A tree-based data structure includes multiple nodes, which are combined based on specific relationships. Each node in a non-empty tree has a key value that uniquely identifies the node. In a binary tree, the key value is represented by the key.
The binary tree is a tree-based data structure where each node has at most two child nodes. Supposing that a node in the binary tree is specified as a parent node, to distinguish the two child nodes of the parent node, the two child nodes are called the left child node and the right child node. In a binary tree, all the nodes and their child nodes are based on this relationship: the key value of a left child node is greater than the key value of its parent node, and the key value of the parent node is greater than the key value of its right child node.
The method for inserting a node into a binary tree is as follows: comparing the key value of the node to be inserted with the key value of the root node of the binary tree, and if the key value of the node to be inserted is smaller than the key value of the root node, inserting the node into the left subtree of the root node, and if not, inserting the node into the right subtree of the root node; comparing the key value of the node to be inserted with the key value of the root node in the left or right subtree, and proceeding like this until the node to be inserted is inserted into the binary tree as a new leaf node. If the shape of the binary tree is fixed (sometimes, it may be understood as the height of the tree is fixed), the insertion of the node into a binary tree as a new leaf node can be interpreted as follows: The node to be inserted is inserted into a virtual position, and then the existing nodes and the nodes to be inserted are transferred based on the relationship that the key value of a left child node is greater than the key value of its parent node and the key value of a parent node is greater than the key value of its right child node.
During the implementation of the present invention, the inventor finds that the prior art has the following defects: If new nodes are to be inserted in a tree with a fixed shape, the existing nodes need to be transferred, and the number of nodes to be transferred exponentially increases with the height of the tree. This causes the increase of the time spent on node insertion sharply. In addition, inserting nodes into the existing tree-based data structure takes too much time.